package class16;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

// OJ链接：https://www.lintcode.com/problem/topological-sorting
public class Code03_TopologicalOrderBFS {

	// 不要提交这个类
	// 定义有向图节点的数据结构
	public static class DirectedGraphNode {
		public int label;  // 节点的标签值
		public ArrayList<DirectedGraphNode> neighbors;  // 节点的邻居列表（出边连接的节点）

		// 构造函数，初始化节点
		public DirectedGraphNode(int x) {
			label = x;
			neighbors = new ArrayList<DirectedGraphNode>();
		}
	}

	// 提交下面的
	// 拓扑排序主函数，使用BFS（Kahn算法）实现
	public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
		// 创建一个Map来存储每个节点的入度（指向该节点的边的数量）
		HashMap<DirectedGraphNode, Integer> indegreeMap = new HashMap<>();
		
		// 初始化：将图中所有节点加入indegreeMap，初始入度设为0
		for (DirectedGraphNode cur : graph) {
			indegreeMap.put(cur, 0);
		}

		// 计算每个节点的实际入度
		// 遍历图中每个节点
		for (DirectedGraphNode cur : graph) {
			// 遍历当前节点的所有邻居（即遍历从当前节点出发的所有边）
			for (DirectedGraphNode next : cur.neighbors) {
				// 将邻居节点的入度加1
				indegreeMap.put(next, indegreeMap.get(next) + 1);
			}
		}
		
		// 创建队列，用于BFS遍历
		Queue<DirectedGraphNode> zeroQueue = new LinkedList<>();
		
		// 将所有入度为0的节点加入队列
		// 入度为0意味着没有节点指向它，可以作为拓扑排序的起点
		for (DirectedGraphNode cur : indegreeMap.keySet()) {
			if (indegreeMap.get(cur) == 0) {
				zeroQueue.add(cur);
			}
		}
		
		// 存储拓扑排序的结果
		ArrayList<DirectedGraphNode> ans = new ArrayList<>();
		
		// 当队列不为空时，继续BFS过程
		while (!zeroQueue.isEmpty()) {
			// 从队列中取出一个入度为0的节点
			DirectedGraphNode cur = zeroQueue.poll();
			// 将该节点加入结果列表
			ans.add(cur);
			
			// 遍历当前节点的所有邻居节点
			for (DirectedGraphNode next : cur.neighbors) {
				// 将邻居节点的入度减1（相当于删除当前节点到邻居节点的边）
				indegreeMap.put(next, indegreeMap.get(next) - 1);
				// 如果邻居节点的入度变为0，说明它不再有前置依赖，可以加入队列
				if (indegreeMap.get(next) == 0) {
					zeroQueue.offer(next);
				}
			}
		}
		
		// 返回拓扑排序的结果
		return ans;
	}

}
